package com.example.demo.Class24_chuangkou;

import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @program: java_base
 * @description: 滑动窗口内的最大值
 * @author: zhouhongtao
 * @happyCreateTime: 2022/03/04 21:48
 */
public class Code01_SlidingWindowMaxArrayDemo {


    static class Node {
        int value;

        public Node(int value) {
            this.value = value;
        }
    }

    /**
     * 规则：
     * 1.数组左L 右R L<=R
     * 2.双端队列内严格是头>尾
     * 3.值相同，还后进入的替换前进入的
     *
     * @param
     * @return
     */
    public void right() {
        Node[] arr = {new Node(1), new Node(3), new Node(100), new Node(50)};
        int L = 0, R = 0;
        int w = 3;
        LinkedList<Integer> queue = new LinkedList();
        queue.addLast(arr[0].value);

        for (int i = 1; i < arr.length; i++) {
            R = i;
            int value = arr[i].value;
            while (!queue.isEmpty() && queue.peekLast() <= value) {
                queue.pollLast();
            }
            queue.add(arr[i].value);
        }
        System.out.println(queue.peekFirst());
    }

    /**
     * 利用索引记录最大位置
     * 输出在 R 滑动时候 w范围内 最大值
     */
    public static int[] getMaxWindow(int[] arr, int w) {
        if (arr == null || arr.length == 0 || w < 1 || arr.length < w) {
            // throw Exception()
            return null;
        }
        LinkedList<Integer> qMax = new LinkedList();
        int[] maxAns = new int[arr.length - w + 1];
        // 1.入队数据，并找到合适的位置
        int index = 0;
        for (int R = 0; R < arr.length; R++) {
            // 尝试入队 当前R位置的元素
            while (!qMax.isEmpty() && arr[qMax.peekLast()] <= arr[R]) {
                qMax.pollLast();
            }
            qMax.addLast(R);
            // 还需要出队一些没有用的 过期元素
            // 比较的是index 看arr的索引是否过期
            if (qMax.peekFirst() == R - w) {
                qMax.pollFirst();
            }
            // 2.看看是否需要更新在w范围内的最大值
            // 每次窗口整体移动 ，更新答案内的最大值
            if (R >= w - 1) {
                maxAns[index++] = arr[qMax.peekFirst()];
            }
        }
        return maxAns;
    }

    public static void main(String[] args) {
        int testTime = 100000;
        int maxSize = 100;
        int maxValue = 100;
        System.out.println("test begin");
        for (int i = 0; i < testTime; i++) {
            int[] arr = generateRandomArray(maxSize, maxValue);
            int w = (int) (Math.random() * (arr.length + 1));
            int[] ans1 = getMaxWindow(arr, w);
            int[] ans2 = right(arr, w);
            if (!isEqual(ans1, ans2)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("test finish");
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * (maxValue + 1));
        }
        return arr;
    }

    // 暴力的对数器方法
    public static int[] right(int[] arr, int w) {
        if (arr == null || w < 1 || arr.length < w) {
            return null;
        }
        int N = arr.length;
        int[] res = new int[N - w + 1];
        int index = 0;
        int L = 0;
        int R = w - 1;
        while (R < N) {
            int max = arr[L];
            for (int i = L + 1; i <= R; i++) {
                max = Math.max(max, arr[i]);

            }
            res[index++] = max;
            L++;
            R++;
        }
        return res;
    }

    // for test
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }
}
